"""
输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-queens
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""
from typing import List


class Solution:
    """回溯"""

    def solveNQueens(self, n: int) -> List[List[str]]:
        ans = []

        def generate_board(row: List[int]):
            board = []
            for i in row:
                tmp = "." * i + "Q" + "." * (n - i - 1)
                board.append(tmp)
            return board

        def backtrack(index: int, row: List[int]):
            """
            index: 行数
            row:   row[i]表示，第i行的纵坐标
            """
            if index == n:
                ans.append(generate_board(row))
                return

            for i in range(n):
                if (not col[i]) and (not dia1[index+i]) and (not dia2[index-i+n-1]):
                    col[i] = True
                    dia1[index+i] = True
                    dia2[index-i+n-1] = True
                    backtrack(index + 1, row + [i])
                    col[i] = False
                    dia1[index+i] = False
                    dia2[index-i+n-1] = False

        col = [False for i in range(n)]
        # n*n的棋盘有2n-1条斜边
        # 从右上到左下的斜边i+j为，0，1，2....
        dia1 = [False for i in range(2*n-1)]
        # 从左上到右下的斜边，规律：
        # 以n=3为例：，i-j的值为[2,1,0,-1,-2],稍微转换一下 i-j+n-1 , 得到[4,3,2,1,0]
        dia2 = [False for i in range(2*n-1)]
        backtrack(0, [])
        return ans


if __name__ == "__main__":
    print(Solution().solveNQueens(4))
